import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-23
 * Time: 22:00
 */
class Position{
    public int x;
    public int y;

    public Position(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        List<List<Position>> pPositions = new ArrayList<>();
        List<Position> positions = new ArrayList<>();
        dfs(n, 0, pPositions, positions);
        // 共有 pPositions.size() 中放法
        for (int i = 0; i < pPositions.size(); i++) {
            List<String> list = new ArrayList<>();
            for (Position position: pPositions.get(i)) {
                // 对字符串的修改需要借助字符数组
                char[] temp = new char[n];
                Arrays.fill(temp, '.');
                temp[position.y] = 'Q';
                list.add(String.valueOf(temp));
            }
            result.add(list);
        }
        return result;
    }

    /**
     * @param n 总的行数
     * @param row 该放第几行了
     * @param pPositions 所有放法的集合
     * @param positions 已经放过的位置的集合
     */
    private void dfs(int n, int row, List<List<Position>> pPositions, List<Position> positions) {
        if(row >= n){
            // 已经放完了, 将这次结果记录
            pPositions.add(new ArrayList<>(positions));
            return ;
        }
        // 开始给这一行放
        for (int i = 0; i < n; i++) {
            boolean flag = true; // 标记能不能放
            // 不满足条件时不能放
            for (Position position : positions) {
                // 肯定不会在同一行
                // 需要考虑的是同一列, 以及同一对角线
                // 同一对角线满足的条件是 横纵坐标和相同或者差相同
                if(i == position.y || row + i == position.x + position.y
                || row - i == position.x - position.y){
                    flag = false;
                    break;
                }
            }
            if(flag){
                // 能放
                positions.add(new Position(row, i));
                dfs(n, row + 1, pPositions, positions);
                // 递归完重新删除, 使用该行的其他位置
                positions.remove(positions.size() - 1);
            }
            // 不能放就继续尝试本行的其他位置
        }
    }
}
